package net.lab1024.sa.admin.module.business.dataStruct.queue.impl;

import net.lab1024.sa.admin.module.business.dataStruct.queue.Queue;

import java.util.Iterator;

public class LinkedListQueue<E> implements Queue<E>, Iterable<E> {

    // 定义结点类：存储值和下一个节点
    private static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    // 头结点（哨兵节点，value固定为null，不存储实际数据）
    private final Node<E> head = new Node<>(null, null);
    // 尾结点（初始指向head）
    private Node<E> tail = head;
    // 队列实际元素数量（新增，避免每次size()都遍历，提升性能）
    private int size = 0;

    // 构造函数：初始化循环链表（tail.next指向head）
    public LinkedListQueue() {
        tail.next = head;
    }

    /**
     * 入队：重复信息不入队，仅存储有效数据
     */
    @Override
    public boolean enqueue(E value) {
        // 1. 过滤null值（避免向队列插入null）
        if (value == null) {
            return false;
        }
        // 2. 重复校验：已存在则不入队
        if (isDuplicate(value)) {
            return false;
        }
        // 3. 正常入队：新增节点，更新tail和size
        Node<E> newNode = new Node<>(value, head); // 新节点的next指向head（维持循环）
        tail.next = newNode;
        tail = newNode;
        size++; // 实际元素数量+1
        return true;
    }

    /**
     * 重复校验：判断队列中是否已存在该值
     */
    public boolean isDuplicate(E target) {
        // 空队列直接返回无重复
        if (isEmpty()) {
            return false;
        }
        // 遍历所有有效节点（从head.next开始，到tail结束）
        Node<E> current = head.next;
        while (current != head) { // 关键：循环到head（哨兵节点）停止，不遍历哨兵
            E currentValue = current.value;
            // 目标值非null，用equals判断（兼容字符串、自定义对象）
            if (target.equals(currentValue)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 出队：移除并返回队首元素（未用到但需修复，保证队列完整性）
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {
            return null; // 空队列返回null（或抛异常，根据业务需求调整）
        }
        Node<E> firstNode = head.next; // 队首有效节点
        E value = firstNode.value;
        // 更新head.next，跳过队首节点
        head.next = firstNode.next;
        // 若队首是最后一个元素，出队后tail需指向head
        if (firstNode == tail) {
            tail = head;
        }
        size--; // 实际元素数量-1
        return value;
    }

    /**
     * 查看队首元素（未用到但需修复）
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }

    /**
     * 队列实际元素数量（修复后：直接返回size变量，无需遍历）
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 判断队列是否为空（修复后：根据size或节点关系判断）
     */
    @Override
    public boolean isEmpty() {
        // 两种判断方式都可：size == 0 或 head.next == head（循环链表空队列标识）
        return size == 0;
    }

    /**
     * 迭代器（核心修复：正确遍历有效节点，不包含哨兵）
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            // 从第一个有效节点开始（head.next）
            private Node<E> current = head.next;

            /**
             * 判断是否有下一个元素：当前节点不是head（哨兵），说明还有有效元素
             */
            @Override
            public boolean hasNext() {
                return current != head;
            }

            /**
             * 返回当前元素，并移动到下一个节点
             */
            @Override
            public E next() {
                E value = current.value;
                current = current.next;
                return value;
            }
        };
    }
    /**
     * 重写toString：返回队列的可视化字符串（格式：[元素1, 元素2, 元素3]）
     * 空队列返回：[]
     */
    @Override
    public String toString() {
        // 1. 空队列直接返回 "[]"
        if (isEmpty()) {
            return "[]";
        }

        // 2. 遍历有效元素，拼接字符串（用StringBuilder提升效率）
        StringBuilder sb = new StringBuilder();
        sb.append("["); // 开头加左括号

        // 遍历所有有效节点（从head.next开始，到head停止，跳过哨兵节点）
        Node<E> current = head.next;
        while (current != head) {
            sb.append(current.value); // 拼接当前元素值
            // 若不是最后一个元素，加逗号和空格（避免末尾多逗号）
            if (current.next != head) {
                sb.append(", ");
            }
            current = current.next;
        }

        sb.append("]"); // 结尾加右括号
        return sb.toString();
    }

}